#include <bits/stdc++.h>

struct SegmentTree1 {
    std::vector<int> ma;
    SegmentTree1(int n) : ma(n * 4, -1) {}
    void range_cmax(int u, int l, int r, int L, int R, int k) {
        if (L <= l && r <= R) {
            ma[u] = std::max(ma[u], k);
            return;
        }
        int mid = (l + r) / 2;
        if (L < mid) range_cmax(u * 2, l, mid, L, R, k);
        if (R > mid) range_cmax(u * 2 + 1, mid, r, L, R, k);
    }
    int query(int u, int l, int r, int p) {
        if (l == r - 1) 
            return ma[u];
        int mid = (l + r) / 2;
        if (p < mid) return std::max(ma[u], query(u * 2, l, mid, p));
        else return std::max(ma[u], query(u * 2 + 1, mid, r, p));
    }
};

struct SegmentTree2 {
    std::vector<int> ma;
    SegmentTree2(int n, const std::vector<int> &a) {
        ma.resize(n * 4);
        std::function<void(int, int, int)> build = [&](int u, int l, int r) {
            if (l == r - 1) {
                ma[u] = a[l];
                return;
            }
            int mid = (l + r) / 2;
            build(u * 2, l, mid);
            build(u * 2 + 1, mid, r);
            ma[u] = std::max(ma[u * 2], ma[u * 2 + 1]);
        };
        build(1, 0, n);
    }
    void modify(int u, int l, int r, int p, int k) {
        if (l == r - 1) {
            ma[u] = k;
            return;
        }
        int mid = (l + r) / 2;
        if (p < mid) modify(u * 2, l, mid, p, k);
        else modify(u * 2 + 1, mid, r, p, k);
        ma[u] = std::max(ma[u * 2], ma[u * 2 + 1]);
    }
    int range_max(int u, int l, int r, int L, int R) {
        if (L <= l && r <= R)
            return ma[u];
        int mid = (l + r) / 2;
        int res = 0;
        if (L < mid) res = std::max(res, range_max(u * 2, l, mid, L, R));
        if (R > mid) res = std::max(res, range_max(u * 2 + 1, mid, r, L, R));
        return res;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, Q;
    std::cin >> n >> m >> Q;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    std::vector<std::pair<int, int>> chg(m);
    for (int i = 0; i < m; ++i) {
        int l, r;
        std::cin >> l >> r;
        --l;
        --r;
        chg[i] = {l, r};
    }
    std::vector<int> op(Q), x(Q), y(Q), z(Q);
    std::vector<std::vector<int>> vec(m);
    for (int i = 0; i < Q; ++i) {
        std::cin >> op[i];
        if (op[i] == 1) {
            std::cin >> x[i] >> y[i];
            --x[i];
        } else {
            std::cin >> x[i] >> y[i] >> z[i];
            --x[i];
            --y[i];
            --z[i];
            vec[y[i]].push_back(i);
        }
    }
    std::vector<int> L(Q), R(Q);
    /* left */ {
        SegmentTree1 tr(n);
        std::vector<std::vector<int>> fa(m, std::vector<int>(18, -1));
        for (int i = 0; i < m; ++i) {
            fa[i][0] = tr.query(1, 0, n, chg[i].first);
            for (int j = 0; j < 17; ++j)
                if (~fa[i][j])
                    fa[i][j + 1] = fa[fa[i][j]][j];
            tr.range_cmax(1, 0, n, chg[i].first, chg[i].second + 1, i);
            for (int j : vec[i]) {
                L[j] = z[j];
                int t = tr.query(1, 0, n, z[j]);
                if (t >= x[j]) {
                    for (int k = 17; ~k; --k)
                        if (~fa[t][k] && fa[t][k] >= x[j])
                            t = fa[t][k];
                    L[j] = chg[t].first;
                }
            }
        }
    }
    /* right */ {
        SegmentTree1 tr(n);
        std::vector<std::vector<int>> fa(m, std::vector<int>(18, -1));
        for (int i = 0; i < m; ++i) {
            fa[i][0] = tr.query(1, 0, n, chg[i].second);
            for (int j = 0; j < 17; ++j)
                if (~fa[i][j])
                    fa[i][j + 1] = fa[fa[i][j]][j];
            tr.range_cmax(1, 0, n, chg[i].first, chg[i].second + 1, i);
            for (int j : vec[i]) {
                R[j] = z[j];
                int t = tr.query(1, 0, n, z[j]);
                if (t >= x[j]) {
                    for (int k = 17; ~k; --k)
                        if (~fa[t][k] && fa[t][k] >= x[j])
                            t = fa[t][k];
                    R[j] = chg[t].second;
                }
            }
        }
    }
    SegmentTree2 tr(n, a);
    for (int i = 0; i < Q; ++i) {
        if (op[i] == 1) {
            tr.modify(1, 0, n, x[i], y[i]);
        } else {
            std::cout << tr.range_max(1, 0, n, L[i], R[i] + 1) << '\n';
        }
    }
    
    return 0;
}